using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace DanielSig
{
	public class InvalidIndexException : Exception
	{
		public InvalidIndexException(String message) : base(message){}
	}
	public sealed class SmartEnumerator<T> : IEnumerator<T>
	{
		public SmartList<T> List;
		public int Index = -1;
		public T Current {
			get {
				return List[Index];
			}
		}
		public bool MoveNext ()
		{
			return ++Index < List.Amount;
		}

		public void Reset ()
		{
			Index = -1;
		}

		object IEnumerator.Current {
			get {
				return (object)List[Index];
			}
		}
		public void Dispose ()
		{
			List = null;
		}
		
	}
	
	[Serializable]
	public class SmartList<T>
	{
		private T[] _list;
		private BitArray _isSlotOccupied;
		private LinkedList<int> _availableIndices = new LinkedList<int>();
		private int _nextIndex = 0;
		private Func<int, int> _resizeFactor;
		
		public SmartList(T[] externalList)
		{
			_list = externalList;
			_isSlotOccupied = new BitArray(externalList.Length);
			_resizeFactor = x => x * 2;
		}
		public SmartList(T[] externalList, Func<int, int> resizeFactor)
		{
			_list = externalList;
			_isSlotOccupied = new BitArray(externalList.Length);
			_resizeFactor = resizeFactor;
		}
		public SmartList()
		{
			_list = new T[8];
			_isSlotOccupied = new BitArray(8);
			_resizeFactor = x => x * 2;
		}
		public SmartList(int capacity)
		{
			_list = new T[capacity];
			_isSlotOccupied = new BitArray(capacity);
			_resizeFactor = x => x * 2;
		}
		public SmartList(int capacity, Func<int, int> resizeFactor)
		{
			_list = new T[capacity];
			_isSlotOccupied = new BitArray(capacity);
			_resizeFactor = resizeFactor;
		}
		
		public int Add(T item)
		{
			int index = _availableIndices.Count > 0 ? _availableIndices.Pop() : _nextIndex++;
			if(index >= _list.Length)
			{
				int newSize = _resizeFactor(_list.Length);
				if(newSize <= _list.Length) throw new ArgumentOutOfRangeException("resizeFactor function must return an integer that is larger than it's input integer");
				IncreaseSize(newSize);
			}
			
			_list[index] = item;
			_isSlotOccupied[index] = true;
			
			return index;
		}
		public bool Contains(T item)
		{
			return _list.IndexOf(item) >= 0;
		}
		public bool Contains(int index)
		{
			return index >= 0 && index < _nextIndex && _isSlotOccupied[index];
		}
		public void Clear()
		{
			_isSlotOccupied.SetAll(false);
			_availableIndices = new LinkedList<int>();
			_nextIndex = 0;
		}
		public void Remove(T item)
		{
			int index = _list.IndexOf(item);
			if(index < 0) throw new ArgumentException(item + " is not in the list but you're trying to remove it");
			RemoveAt(_list.IndexOf(item));
		}
		public void RemoveAt(int index)
		{
			if(index < 0) throw new IndexOutOfRangeException("index must be 0 or greater but it was " + index);
			if(index >= _nextIndex) throw new IndexOutOfRangeException("index " + index + " is out of bounds");
			if(!_isSlotOccupied[index]) throw new InvalidIndexException("there is no " + typeof(T).ToString() + " to be removed from the list at index " + index);
			
			_list[index] = default(T);
			_isSlotOccupied[index] = false;
			
			if(index == _nextIndex - 1) _nextIndex--;
			else _availableIndices.Push(index);
		}
		public T TryGetAt(int index)
		{
			if(index < 0) return default(T);
			if(index >= _nextIndex) return default(T);
			if(_isSlotOccupied[index]) return _list[index];
			return default(T);
		}
		public T this[int index]
		{
			get
			{
				if(index < 0) throw new IndexOutOfRangeException("index must be 0 or greater");
				if(index >= _nextIndex) throw new IndexOutOfRangeException("index " + index + " is out of bounds");
				if(_isSlotOccupied[index]) return _list[index];
				else throw new InvalidIndexException("there is no " + typeof(T).ToString() + " in the list at index " + index);
			}
			set
			{
				if(index == _nextIndex) Add(value);
				else
				{
					if(index < 0) throw new IndexOutOfRangeException("index must be 0 or greater");
					if(index >= _list.Length)
					{
						IncreaseSize(index + 1);
					}
					else//it is only when the index is smaller than the capacity that conflicts can occur
					{
						if(_isSlotOccupied[index]) throw new InvalidIndexException("Could not place " + value + " at index " + index + " because it is already occupied by " + _list[index]);
					}
					
					if(_nextIndex < index)
					{
						while(_nextIndex < index)
						{
							_availableIndices.Push(_nextIndex++);
						}
					}
					else
					{
						_availableIndices.RemoveOne(x => x != index);
					}
					
					_list[index] = value;
					_isSlotOccupied[index] = true;
				}
			}
		}
		private void IncreaseSize(int newSize)
		{
			Array.Resize<T>(ref _list, newSize);
			
			int[] bits = new int[((newSize - 1) >> 3) + 1];
			_isSlotOccupied.CopyTo(bits, 0);
			_isSlotOccupied = new BitArray(bits);
		}
		
		public int Amount//amount is used since, the size of the list doesn't equal the amount of items in it
		{
			get
			{
				return _nextIndex - _availableIndices.Count;
			}
		}
		public int Capacity
		{
			get
			{
				return _nextIndex;
			}
		}
		public T[] RawArray
		{
			get
			{
				return _list;
			}
		}
		public SmartEnumerator<T> GetEnumerator()
		{
			SmartEnumerator<T> enumerator = new SmartEnumerator<T>();
			enumerator.List = this;
			return enumerator;
		}
	}
}

